#include "Format.h"

class HeapSort {
public:
    HeapSort();

   HeapSort(int *arr, int num) {
        HeapSort();
        this->sort(arr, num);
        Format::format(arr, num);
    }
    ~HeapSort();

private:
    int sort(int arr[], int num);
    void HeapAdjust(int array[], int i, int Length);
};

HeapSort::HeapSort() {
}

HeapSort::~HeapSort() {
}

void HeapSort::HeapAdjust(int arr[], int i, int Length) {
    int moveCount = 0, compareCount = 0;
    int Child = 0;
    int Temp;
    for (; 2 * i + 1 < Length; i = Child) {
        //i���ĸ�����±��Ϊ(i �C 1) / 2�����������ӽ���±�ֱ�Ϊ2 * i + 1��2 * i + 2
        Child = 2 * i + 1;
        moveCount++;
        //�õ��ӽ���нϴ�Ľ��
        if (Child < Length - 1 && arr[Child + 1] > arr[Child]) {
            ++Child;
            moveCount++;
        }
        //����ϴ���ӽ����ڸ������ô�ѽϴ���ӽ�������ƶ����滻���ĸ����
        compareCount++;

        if (arr[i] < arr[Child]) {
            Temp = arr[i];
            arr[i] = arr[Child];
            arr[Child] = Temp;
            moveCount += 3;
        } else {
            break; //�����˳�ѭ��
        }
        compareCount++;
    }
    compareCount++;
    arr[TestNumber] += moveCount;
    arr[TestNumber + 1] += compareCount;
}

int HeapSort::sort(int *arr, int Length) {
    int moveCount = 0, compareCount = 0, i, j, k, temp;

    //�������е�ǰ�벿��Ԫ�أ�������֮���һ��Ԫ�������е�����Ԫ��
    //length/2-1�����һ����Ҷ�ڵ㣬�˴�"/"Ϊ����
    for (i = Length / 2 - 1; i >= 0; i--) {
        HeapAdjust(arr, i, Length); //��Ϊ��������֧����Ҫ����
    }

    for (i = Length - 1; i > 0; i--) {//ȡ������һ������������β����Ȼ�����µ�����
        temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        HeapAdjust(arr, 0, i);
    }
    arr[Length] += moveCount;
    arr[Length + 1] += compareCount;

    return 0;
}



